from collections import deque

with open("board.txt") as f:
    content = f.read().strip()
content = content.split('\n')
board = []
for col in content:
    board.append(list(col))

m, n = len(board), len(board[0])
for i in range(m):
    for j in range(n):
        if board[i][j] == 'A':
            start = (i,j)
        elif board[i][j] == 'B':
            destination = (i, j)

def dfs():
    visited = [[False for _ in range(n)] for _ in range(m)]
    def _dfs(x,y, road):
        if (x,y) == destination:
            print(f'{road}->{x,y}')
            return
        for nx, ny in [(x+1, y),(x-1,y),(x,y+1),(x,y-1)]:
            if nx < 0 or nx >= m: continue
            if ny < 0 or ny >= n: continue
            if visited[nx][ny]: continue
            if board[nx][ny] =='#': continue
            visited[nx][ny] = True
            _dfs(nx,ny,f'{road}->{nx,ny}')
    _dfs(start[0],start[1], str(start))


def bfs():
    q = deque([])
    q.append([start[0], start[1]])
    parent = [[None for _ in range(n)] for _ in range(m)]
    while q:
        x,y = q.popleft()
        if (x,y) == destination:
            break
        for nx, ny in [(x+1, y),(x-1,y),(x,y+1),(x,y-1)]:
            if nx < 0 or nx >= m: continue
            if ny < 0 or ny >= n: continue
            if board[nx][ny] =='#': continue
            if parent[nx][ny]: continue
            parent[nx][ny] = (x,y)
            q.append([nx,ny])
    stack = []
    x, y=  destination
    while parent[x][y] != start:
        stack.append((x, y))
        x, y = parent[x][y]
    print(f"{start}->", end='')
    print('->'.join(map(str, stack[::-1])))

bfs()
